package io.adrainty.algorithm.leetcode.lcr;

/**
 * LCR 013. 二维区域和检索 - 矩阵不可变
 * @link <a href="https://leetcode.cn/problems/O4NDxx/">...</a>
 * @author AdRainty
 * @version V1.0.0
 * @since 2024/9/8 下午10:17
 */
public class LCR013 {

    private LCR013() {}

    public static class NumMatrix {

        private final int[][] sums;

        public NumMatrix(int[][] matrix) {
            this.sums = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (i == 0 && j == 0) {
                        sums[i][j] = matrix[i][j];
                    } else if (i == 0) {
                        sums[i][j] = sums[i][j - 1] + matrix[i][j];
                    } else if (j == 0) {
                        sums[i][j] = sums[i - 1][j] + matrix[i][j];
                    } else {
                        sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + matrix[i][j];
                    }
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            if (row1 == 0 && col1 == 0) return sums[row2][col2];
            if (row1 == 0) return sums[row2][col2] - sums[row2][col1 - 1];
            if (col1 == 0) return sums[row2][col2] - sums[row1 - 1][col2];
            return sums[row2][col2] - sums[row1 - 1][col2] - sums[row2][col1 - 1] + sums[row1 - 1][col1 - 1];
        }
    }

}
